#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <conio.h>
using namespace std;

void find_maximal_alternative_subseq_and_indexes(const vector<int> &in_seq, const vector<int> *first_length_seq, 
	const vector<int> *second_length_seq, bool less, vector<int> &res, vector<int> &indexes)
{
	auto max_len_it = max_element(first_length_seq->begin(), first_length_seq->end());
	int current_searched_length = *max_len_it - 1;
	int i_idx = distance(first_length_seq->begin(), max_len_it);

	while (1)
	{
		int cur_elem = in_seq[i_idx],
			prev_i_idx = i_idx;
		res.push_back(cur_elem);
		indexes.push_back(i_idx);

		for (int i_sub_idx = i_idx-1; i_sub_idx >= 0; --i_sub_idx)
		{
			if ((*second_length_seq)[i_sub_idx] == current_searched_length)
			{
				if (less && in_seq[i_sub_idx] < cur_elem)
				{
					i_idx = i_sub_idx;					
				}
				else if (!less && in_seq[i_sub_idx] > cur_elem)
				{
					i_idx = i_sub_idx;
				}
			}
		}

		if (i_idx == prev_i_idx)
			break;

		less = !less;
		current_searched_length--;
		swap(first_length_seq, second_length_seq);
	}
}

// for each element maintain two numbers:
// 1) the length of the longest alternative subsequence, where this element is bigger, than previous one (which is
// lesser than prev prev)
// 2) the length of the longest alternative subsequence, where this element is lesses, than the previous one (which is
// bigger than prev prev)
void find_maximal_alternation_subsequence(const vector<int> &in_seq, vector<int> &out_subseq)
{
	vector<int> less_length(in_seq.size(), 1),
		bigger_length(in_seq.size(), 1);

	if (in_seq.size() == 0)
		return;

	for (int i_in = 1; i_in < static_cast<int>(in_seq.size()); ++i_in)
	{
		int cur_elem = in_seq[i_in];
		for (int i_subseq = i_in-1; i_subseq >= 0; --i_subseq)
		{
			if (cur_elem < in_seq[i_subseq])
			{
				if (less_length[i_in] <= bigger_length[i_subseq])
				{
					less_length[i_in] = bigger_length[i_subseq] + 1;
				}
			}
			else if (cur_elem > in_seq[i_subseq])
			{
				if (bigger_length[i_in] <= less_length[i_subseq])
				{
					bigger_length[i_in] = less_length[i_subseq] + 1;
				}
			}
		}
	}

	vector<int> res_1, indexes_1;
	find_maximal_alternative_subseq_and_indexes(in_seq, &less_length, &bigger_length, false, res_1, indexes_1);

	vector<int> res_2, indexes_2;
	find_maximal_alternative_subseq_and_indexes(in_seq, &bigger_length, &less_length, true, res_2, indexes_2);

	if (res_1.size() > res_2.size())
		out_subseq = res_1;
	else if (res_1.size() < res_2.size())
		out_subseq = res_2;
	else
	{
		for (int i = 0; i < static_cast<int>(res_1.size()); i++)
		{
			if (indexes_1[i] < indexes_2[i])
			{
				out_subseq = res_1;
				break;
			}
			else if (indexes_1[i] > indexes_2[i])
			{
				out_subseq = res_2;
				break;
			}
		}
	}
}

void main()
{
	cout << "input sequence size : " << endl;
	int n;
	cin >> n;

	cout << "input sequence: " << endl;
	vector<int> seq(n);
	for (int i = 0; i < n; i++)
		cin >> seq[i];

	vector<int> out_seq;
	find_maximal_alternation_subsequence(seq, out_seq);

	cout << endl << "maximal alternative subsequence:" << endl;
	for (auto it_elem = out_seq.rbegin(); it_elem != out_seq.rend(); ++it_elem)
		cout << *it_elem << " ";

	cout << endl << "Press any key : " << endl;
	_getch();
}